/*
 * @lc app=leetcode.cn id=142 lang=swift
 *
 * [142] 环形链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func detectCycle(_ head: ListNode?) -> ListNode? {
        var s = head, q = head
        while q != nil, q?.next != nil {
            s = s?.next
            q = q?.next?.next
            if s === q {
                s = head
                while s !== q {
                    s = s?.next
                    q = q?.next
                }
                return s
            }
        }
        return nil
    }
}
// @lc code=end

